/* License Notice:
**
** This program is free software: you can redistribute it and/or modify
**    it under the terms of the GNU General Public License as published by
**    the Free Software Foundation, either version 3 of the License, or
**    (at your option) any later version.
** This program is distributed in the hope that it will be useful,
**   but WITHOUT ANY WARRANTY; without even the implied warranty of
**   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
**   GNU General Public License for more details.
** You should have received a copy of the GNU General Public License
**   along with this program. If not, see <https://www.gnu.org/licenses/>.
*/

/**
 * @file linked_list_fast.hpp
 * @author TooOld2Rock'nRoll
 * @date dec/2004
 * @version 4.0.0
 *
 * @attention "make CFLAGS:=-DUNIT_TESTING" to run unit testing on the library.
 *
 * @see Cormen, Thomas H. (...) - Introduction to Algorithms (2ºed)
 * @see Deitel, H. M. (...) - How to Program C++ (3ªed)
 * @see https://cpputest.github.io/manual.html
 *
 * @todo maybe add a sort function.
 * @bug remove will break if iterator started in a different node than the head!! (aux will be null but not the first)
 * @bug search will get stuck on same node if run consecutively to search other nodes with same key.
 *
 * @brief Header file for the <i>fast</i> version Linked List data structure.
 */
#ifndef LLIST_F_HPP
#define LLIST_F_HPP

/*---- Includes ----*/
#include <stdexcept>
#include <fmt/core.h>

#ifdef UNIT_TESTING
#include <CppUTest/CommandLineTestRunner.h>
#include <CppUTest/MemoryLeakDetectorNewMacros.h>
#endif

/*---- Class Declaration ----*/
/**
 * @brief Fast Linked List data structure.
 * @see https://en.wikipedia.org/wiki/Linked_list
 *
 * @warning You <b>are</b> responsible for allocating and deallocating the memory for the node packages in some
 *    operations since the library doesn't copie the user packages (it only saves references to).
 *
 * A linked list is a dynamic collection of (usually) unordered nodes that are accessed sequentially from head to tail.<br>
 *
 * This algorithm is fast in the sense that it only saves references to user data, but this is not safe and difficult to
 *   debug in case of errors. Consider using the Safe version if such safeguards are necessary in your project.<br>
 * It is, however, thread compliant! It is not guaranteed to be consistent under any conditions, but the iterators
 *   permit to read/write at any position independently. It is more practical though to implement the common safeguards
 *   for threads at the user level than here, it would be quite a hassle to control every search operation combined with
 *   every remove operation for each node being read at any time at this side of the fence!<br>
 *
 * The insert() function adds a new node to the list head.<br>
 * The remove() function takes out a list's node at the head or over the iterator.<br>
 * The next() function moves the iterator forward.<br>
 * The other functions are just helpers that make some jobs easier.<br>
 * A report will be printed on destruct if ENABLE_BENCHMARK flag is active.<br>
 *
 * Example:
 * <code>
 *   int *x = nullptr, *buff = nullptr;
 *   LinkedList TheList;
 *
 *   x = new int (10);
 *   TheList.insert (x);
 *
 *   x = new int (20);
 *   TheList.insert (x);
 *
 *   //remove second package (the one under the read head)
 *   buff = TheList.remove (TheList.search (TheList.beggin (), 20));
 *   //buff == 20
 *   delete (buff);
 *
 *   //10 remains and will be dealt with in the destructor.
 *
 *   //a report may be printed
 * </code>
 *
 *  -Statistics:<br>
 *      Total Used Time: 11.3860s
 *          Insert
 *            -was called 50000 times.
 *            -total used time: 0.004000s
 *            -Average Delay: 0.000080ms
 *          Remove
 *            -was called 50000 times.
 *            -total used time: 0.006000s
 *            -Average Delay: 0.000120ms
 *          Search
 *            -was called 50000 times.
 *            -total used time: 11.376000s
 *            -Average Delay: 0.227520ms
 *     -Machine Specs:<br>
 *        Intel Core i7-7700HQ CPU @ 2.80GHz<br>
 *        16Gb RAM<br>
 *
 * @tparam T - data type to be stored in the list.
 */
template <typename T>
class LinkedList
{
    private:
        //the node structure that builds the list
        struct node_s
        {
            T *_package = nullptr; //user data
            node_s *_next = nullptr; //pointer to next node or null if last one
        };//end node

        std::size_t _size = 0;//the number of nodes in the list

        node_s *_head = nullptr; //first node of the list or null if empty


    protected:


    public:
        /**
         * @brief Permits the list to be traversed using a independent iterator that looks one node at a time.
         * @remarks std::iterator is deprecated, instead it works now with concepts, so we have to "just point into the
         *    right direction" and the compiler understands the intention behind it.
         * @see https://en.cppreference.com/w/cpp/iterator/iterator
         * @see https://en.cppreference.com/w/cpp/language/constraints
         */
        class iterator
        {
            friend class LinkedList;

            public:
                ///The category of the iterator, one of https://en.cppreference.com/w/cpp/iterator/iterator_tags
                using iterator_category = std::forward_iterator_tag;
                using difference_type   = std::ptrdiff_t; ///<How to identify distance between iterators.
                using value_type        = T; ///<The dereferenced iterator type.
                using pointer           = T*; ///<Defines a pointer the iterator data type.
                using reference         = T&; ///<Defines a reference the iterator data type.

            private:
                LinkedList::node_s *_readhead = nullptr; //current node being read
                LinkedList::node_s *_aux_node = nullptr; //keeps track of previous node, required for remove!

            public:
                /** @brief Default Constructor. */
                iterator () { }
                /** @brief Constructor.
                 * @param head- reference to the beginning of the list. */
                iterator (LinkedList::node_s *head) { this->_readhead = head; }

                /** @brief What to return when the iterator pointer is requested. */
                iterator operator*() const { return *this; }

                // pointer operator->() { return this->read (); }

                /** @brief Increments the iterator position to the next node. */
                iterator& operator++()
                { this->next ();
                  return *this; }

                /** @brief Reads the iterator contents and than increments the iterator position to the next node.
                 *  @warning It depends on a static reference to the previous node, I can't think of a way around this
                 *      since we are dealing with iterators that point to "states" of a larger thing. The consequence is
                 *      that the return value of this operation can't be trusted for long. */
                iterator& operator++(int)
                { static iterator retval;
                  retval = *this;
                  this->next ();
                  return retval; }

                /** @brief Compares the contents of two iterators (not the package value!).
                 * @return <b>true</b> if the two nodes are equal; <b>false</b> if different. */
                bool operator== (const iterator &other) const {return this->_readhead == other._readhead;}

                /** @brief Compares the contents of two iterators (not the package value!).
                 * @return <b>true</b> if the two nodes are different; <b>false</b> if equal. */
                bool operator!= (const iterator &other) const {return !(*this == other);}

                pointer read () const;
                pointer next ();
                pointer swap (pointer new_package);
        };//end class Iterator

        LinkedList ();
        ~LinkedList ();

        void insert (T *new_package);
        T* remove ();
        T* remove (LinkedList::iterator &it);

        LinkedList<T>::iterator* search (LinkedList<T>::iterator &begin, T &key);

        void clean (bool del_packages);

        /** @brief Returns <b>true</b> if list is empty, <b>false</b> otherwise. */
        bool empty () const { return (this->_size == 0); }
        /** @brief Returns the number of nodes stored in the list. */
        std::size_t size () const { return this->_size; }

        /** @brief Gets an Iterator to the beginning of the list. */
        LinkedList<T>::iterator begin () { return iterator(this->_head); }
        /** @brief Gets an Iterator to the end of the list. */
        const LinkedList<T>::iterator & end ()
        { static LinkedList<T>::iterator it(nullptr);
          return it; }

#ifdef ENABLE_BENCHMARK
        void benchmarkReport ();
#endif
};//END LinkedList

#endif //LLIST_F_HPP

